import java.util.*;
/**
 * @program: leetcode022
 * @author: JCM
 * @create: 2022-11-21 10:35
 * @description:
 **/
public class leetCode022 {
    /**
     * 回溯法
     * @param n
     * @return
     */
    public List<String> generateParenthesis1(int n) {
        List<String> res = new ArrayList<>();
        backtrack(res,new StringBuffer(), 0, 0, n);
        return res;
    }

    /**
     *
     * @param res
     * @param sb 括号字符串
     * @param open 左括号
     * @param close 右括号
     * @param max 括号的最大数量
     */
    public void backtrack(List<String> res,StringBuffer sb,int open,int close,int max) {
        if(sb.length() == max*2) {
            res.add(sb.toString());
        }
        if(open < max) {
            sb.append('(');
            backtrack(res,sb,open+1,close,max);
            sb.deleteCharAt(sb.length()-1);
        }
        if(close < open) {
            sb.append(')');
            backtrack(res,sb,open,close+1,max);
            sb.deleteCharAt(sb.length()-1);
        }
    }

    public static void main(String[] args) {
        int n = 3;
        List<String> ans = generateParenthesis(n);
    }

    /**
     * 暴力枚举
     * @param n
     * @return
     */
    public static List<String> generateParenthesis(int n) {
        List<String> combinations = new ArrayList<String>();
        generateAll(new char[2 * n], 0, combinations);
        return combinations;
    }

    private static void generateAll(char[] cur, int pos, List<String> res) {
        //左右括号全部加完
        if(pos == cur.length) {
            //判断括号是否合法
            if(valid(cur)) {
                res.add(new String(cur));
            }
        }else {
            cur[pos] = '(';
            generateAll(cur,pos+1,res);
            cur[pos] = ')';
            generateAll(cur,pos+1,res);
        }
    }

    /**
     * 判断 括号是否合法
     * @param cur
     * @return
     */
    private static boolean valid(char[] cur) {
        int balance = 0;
        for (char c: cur) {
            if(c == '(') {
                balance++;
            }else {
                balance--;
            }
            if(balance < 0) {
                return false;
            }
        }
        return  balance == 0;
    }

}
